package 滑动窗口.无重复最长子串;
/**
 * 题目描述:
 * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
 * 输入: s = "abcabcbb"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。注意 "bca" 和 "cab" 也是正确答案。
 * 力扣：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
 * 力扣第3题
 * */
/**
 * 题目思路：
 * 暴力解法：
 * 创建一个布尔数组，用于标记字符是否出现过。
 * 双层for循环
 * 第一层循环，把s[i]当做当前子串的右端点
 * 第二层循环，从i往左退，试图扩展出尽可能长的，不含重复字符的子串
 * 用book记录当前字符出现的子串中出现的字符
 * 一旦发现就break
 * 每次更新：当前以i结尾的最长无重复子串长度 = i - j + 1
 * 全局取最大值 res
 * */

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int res = 0; // 用来存储最常子串的长度
        // 外层循环，从字符的第一个字符开始
        for(int i = 0;i < s.length();i++){
            boolean[] book = new boolean[300]; // 布尔数组，用于标记字符是否出现过,book里面全是false

            // 内层循环，从当前字符向前遍历
            for(int j = i; j >= 0;j--){
                // 如果字符已经在子串中出现过，结束内层循环
                if(book[s.charAt(j)]){
                    break;
                }
                // 标记当前字符为出现过
                book[s.charAt(j)] = true;
                // 更新最长子串长度
                res = Math.max(res,i - j + 1);
            }
        }
        return res;// 返回最长子串长度
    }
}